package com.base.dataStructure.linkedlist;

import lombok.AllArgsConstructor;
import lombok.Data;

import java.util.Iterator;

/**
 * @Author: hdhao
 * @Create: 2023/3/27 - 22:33
 * @Version: v1.0
 */
//双向链表
public class DoublyLinkedListSentinel implements Iterable<Integer>{
    private Node head;//头哨兵
    private Node tail;//尾哨兵

    public DoublyLinkedListSentinel(){
        head = new Node(null,666,null);
        tail = new Node(null,888,null);
        head.next = tail;
        tail.prev = head;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = head.next;
            @Override
            public boolean hasNext() {
                return p!=tail;
            }

            @Override
            public Integer next() {
                int value = p.value;
                p = p.next;
                return value;
            }
        };
    }

    @Data
    @AllArgsConstructor
    private static class Node{
        Node prev;//上一个节点的指针
        int value;//存储的值
        Node next;//下一个节点的指针
    }

    /**
     * 向双向链表中插入新的节点
     * @param index
     * @param value
     */
    public void insert(int index,int value){
        //待插入节点的上一个节点
        Node prev = findNode(index - 1);
        if (prev == null){
            throw new RuntimeException("index is illegal");
        }
        //待插入节点的下一个节点
        Node next = prev.next;
        //创建出要插入的节点
        Node inserted = new Node(prev, value, next);
        //待插入节点的上一个节点的next指向新节点
        prev.next = inserted;
        //待插入节点的下一个节点的prev指向新节点
        next.prev = inserted;
    }

    /**
     * 添加头结点
     * @param value
     */
    public void addFirst(int value){
        insert(0,value);
    }

    /**
     * 根据索引删除节点
     * @param index
     */
    public void remove(int index){
        //待删除元素的上一个节点
        Node prev = findNode(index - 1);
        if (prev == null){
            throw new RuntimeException("index is illegal");
        }
        //待删除元素
        Node removed = prev.next;
        //如果待删除元素是尾哨兵时抛出异常
        if (removed == tail){
            throw new RuntimeException("index is illegal");
        }
        //待删除元素的下一个节点
        Node next = removed.next;
        //待删除元素的上一个节点的next指向待删除元素的下一个节点
        //(不再指向待删除元素)
        prev.next = next;
        //待删除元素的下一个节点的prev指向待删除元素的上一个节点
        //(不再指向待删除元素)
        next.prev = prev;
    }

    /**
     * 删除头结点
     */
    public void removeFirst(){
        remove(0);
    }

    /**
     * 添加尾结点
     * @param value
     */
    public void addLast(int value){
        //原尾结点
        Node last = tail.prev;
        Node added = new Node(last, value, tail);
        last.next = added;
        tail.prev = added;
    }

    /**
     * 删除尾结点
     */
    public void removeLast(){
        Node removed = tail.prev;
        if (removed == head){
            throw new RuntimeException("index is illegal");
        }
        Node prev = removed.prev;
        prev.next = tail;
        tail.prev = prev;
    }
    /**
     * 根据索引位置找到节点
     * @param index
     * @return
     */
    private Node findNode(int index){
        //index=-1时表示是头哨兵节点
        int i = -1;
        //遍历链表,当指针 = 尾哨兵节点时 退出循环
        for (Node p = head; p != tail; p = p.next,i++){
            if (i == index){
                return p;
            }
        }
        return null;
    }
}
